package com.wanghe.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * 最小编辑距离(即Levenshtein Distance)
 */
public class MinimumEditDistance {

    private static final Map<String, Integer> results = new HashMap<>();

    public static void main(String[] args) {

        String s1 = "a";
        String s2 = "ab";
        System.out.println(distance(s1, s2, s1.length(), s2.length()));

    }

    /**
     * 计算两个指定子串的编辑距离
     *
     * @param s1 第一个字符串
     * @param s2 第二个字符串
     * @param p1 第一个子串的结尾(即s1[1...p1]), 第一个字符的位置为1
     * @param p2 第二个子串的结尾(即s2[1...p2])，第一个字符的位置为1
     * @return 两个子串之间的编辑距离
     */
    private static int distance(String s1, String s2, int p1, int p2) {

        String key = "" + p1 + "#" + p2;
        Integer result = results.get(key);
        if (result != null) {
            return result;
        }

        if (0 == p1) {
            return p2;
        }
        if (0 == p2) {
            return p1;
        }
        char c1 = s1.charAt(p1 - 1);
        char c2 = s2.charAt(p2 - 1);
        if (c1 == c2) {
            return distance(s1, s2, p1 - 1, p2 - 1);
        }
        result = min3Values(distance(s1, s2, p1 - 1, p2) + 1,
                          distance(s1, s2, p1, p2 - 1) + 1,
                          distance(s1, s2, p1 - 1, p2 - 1) + 1);
        results.put(key, result);
        return result;
    }

    private static int min3Values(int v1, int v2, int v3) {
        int tmp = Integer.MAX_VALUE;
        if (v1 < tmp) {
            tmp = v1;
        }
        if (v2 < tmp) {
            tmp = v2;
        }
        if (v3 < tmp) {
            tmp = v3;
        }
        return tmp;
    }

}
